package com.leetcode.algorithm.y22.m08.w2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 49. 字母异位词分组
 * 
 * https://leetcode.cn/problems/group-anagrams/
 * 
 * @author jie.deng
 *
 */
class Question0049Solution02 {

	public List<List<String>> groupAnagrams(String[] strs) {
		int len = strs.length;
		if (len == 0) {
			return new ArrayList<>();
		}

		String[] ascStrs = new String[len];
		Map<String, List<String>> map = new HashMap<>();
		for (int i = 0; i < len; i++) {
			char[] chArr = strs[i].toCharArray();
			Arrays.sort(chArr);
			ascStrs[i] = new String(chArr);

			List<String> list = map.get(ascStrs[i]);
			if (list == null) {
				list = new ArrayList<>();
				map.put(ascStrs[i], list);
			}
			list.add(strs[i]);
		}

		return new ArrayList<>(map.values());
	}

}